Stack

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. Imagine a stack of plates: the last plate placed on top is the first one to be taken off. In a stack, all insertions and deletions occur at one end, called the "top" of the stack.

Basic Operations and Their Complexity

Operation	Description	Time Complexity
Push	Adds an element to the top of the stack	$O(1)$
Pop	Removes the element from the top of the stack	$O(1)$
Peek	Returns the top element without removing it	$O(1)$
isEmpty	Checks if the stack is empty	$O(1)$
isFull	Checks if the stack is full (for bounded stacks)	$O(1)$

Implementing a Stack

Using a Linked List

In a linked list-based stack, the head node represents the top of the stack. Elements are added and removed from the head, ensuring constant time operations.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedListStack:
    def __init__(self):
        self._top = None
        self._size = 0

    def size(self) -> int:
        return self._size

    def is_empty(self) -> bool:
        return self._top is None

    def push(self, val: int):
        node = ListNode(val, self._top)
        self._top = node
        self._size += 1

    def pop(self) -> int:
        if self.is_empty():
            raise IndexError("Stack is empty")
        val = self._top.val
        self._top = self._top.next
        self._size -= 1
        return val

    def peek(self) -> int:
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._top.val

    def to_list(self) -> list[int]:
        arr = []
        current = self._top
        while current:
            arr.append(current.val)
            current = current.next
        arr.reverse()
        return arr

Using an Array (List)

In an array-based stack, the end of the array is considered the top of the stack. Elements are added and removed from the end, making push and pop operations efficient.

class ArrayStack:
    def __init__(self):
        self._stack = []

    def size(self) -> int:
        return len(self._stack)

    def is_empty(self) -> bool:
        return not self._stack

    def push(self, item: int):
        self._stack.append(item)

    def pop(self) -> int:
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._stack.pop()

    def peek(self) -> int:
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._stack[-1]

    def to_list(self) -> list[int]:
        return self._stack.copy()

Comparison of the Two Implementations

Supported Operations

Both implementations support all standard stack operations with the same time complexity. The array-based stack allows indexing, but random access is not typical in stack usage.

Time Efficiency

• Array-Based Implementation:
  • Push and Pop: Generally faster due to better cache performance.
  • Resizing Overhead: May require resizing the array, leading to occasional $O(n)$ operations. However, with dynamic arrays, this cost is amortized over many operations.
• Linked List-Based Implementation:
  • Push and Pop: Consistent $O(1)$ time without resizing.
  • Overhead: Slightly slower due to dynamic memory allocation for each node.

Space Efficiency

• Array-Based Implementation:
  • Memory Usage: May allocate more memory than needed due to pre-allocation and resizing strategies.
  • Per Element Overhead: Minimal, as only the data is stored.
• Linked List-Based Implementation:
  • Memory Usage: Uses exactly as much memory as needed for the elements.
  • Per Element Overhead: Additional memory for the pointer in each node.

Advantages and Disadvantages

Advantages

• Simplicity: Easy to implement and understand.
• Efficiency: Push and pop operations are $O(1)$.
• Memory Management: Useful for managing function calls and local variables, especially in recursive algorithms.

Disadvantages

• Limited Access: Only the top element is accessible directly.
• Fixed Size (Array-Based): May lead to overflow unless dynamic resizing is implemented.
• Memory Overhead (Linked List-Based): Additional memory is required for pointers.

Applications

• Expression Evaluation: Evaluating postfix or prefix expressions.
• Expression Conversion: Converting infix expressions to postfix or prefix.
• Syntax Parsing: Used in compilers for syntax checking.
• Backtracking: Implementing undo operations in software.
• Memory Management: Managing function calls in recursive programming.
• Depth-First Search (DFS): Used in graph traversal algorithms.

Example: Balancing Parentheses

Stacks are used to check for balanced parentheses in an expression.

def is_balanced(expression: str) -> bool:
    stack = []
    pairs = {'(': ')', '{': '}', '[': ']'}
    for char in expression:
        if char in pairs:
            stack.append(char)
        elif char in pairs.values():
            if not stack or pairs[stack.pop()] != char:
                return False
    return not stack

# Example usage
expression = "{[()()]}"
print(is_balanced(expression))  # Output: True

Explanation:

• Initialization: An empty list stack is used to simulate stack behavior.
• Iteration: For each character in the expression:
  • Opening Brackets: If the character is an opening bracket, push it onto the stack.
  • Closing Brackets: If it's a closing bracket, check if the top of the stack matches. If not, return False.
• Completion: After processing, if the stack is empty, the expression is balanced.